Previously, secret communications were secured either by secret-key (also called symmetric key) cyphers, public key (also called asymmetric) encryption, or by a combination of them. Public key cryptography allows public keys to be distributed and even published while limiting the decryption (and signing) possibilities to the owner of the private key only. Secret key communication is more efficient computationally. Also, a specific type of secret key cryptography, known as one time pad, is unconditionally secure (from the cryptographic point of view) provided only that the key remains secret. The foregoing schemes ensure confidentiality of the messages. However in some situations, such as election systems or anonymous payment systems, not only the contents of the communication should be secured, but also the identity of each sender.
It is difficult to separate information about the sender from the contents of the message itself. Consequently, it is difficult to make the identity of the sender anonymous but the contents of the message available to the recipient and secret to an intermediate party.
In known symmetric encryption, a key is distributed securely to another participant and both participants keep a copy of the same key. The sender encrypts the message with the key and sends the encrypted message to the recipient. The recipient then decrypts the message with the key. In this scheme, the recipient knows the identity of the sender of the message. Consequently, if the message is a vote, the recipient would know the identity of the voter because the recipient has sufficient knowledge to make the link between the voter and his or her vote. One solution is to have intermediate agents between the sender and the recipient. Such a system based on public key cryptography is described in the article by David Chaum “Untraceable electronic Mail, Return Addresses, and Digital Pseudonyms” Comm ACM 24, 2, Feb. 1981, 84-88, wherein the author proposes to divide the recipients among different agents. For example, with two agents, the sender transmits his or her encrypted message encrypted with a series of public keys to one of the agents. This one agent decrypts the message with his or her private key only, and in turn sends the result to another agent without telling this other agent the identity of the sender.
The same strategy can be extended a system with many agents. This system will achieve anonymity provided all the agents do not collude, because intermediate agents can only pass on public keys to the sender, without being able to decrypt the messages. However, this system has the typical limitations of public key encryption:                this system lacks an unconditionally secure protocol (for elections this will be an argument).        this system is computationally demanding.        this system does not prevent vote buying, because a voter can prove his vote.        this system cannot be performed by humans only; it requires use of electronic devices in all circumstances.        
If secret keys are used, there is still the problem of giving the sender the requisite keys such that the recipient does not know the identity of the sender but can decrypt the message while intermediate agents cannot. In this scheme, with two agents, a first agent gives a key to a second agent. Then, the second agent adds a key of his or her own and forwards the key to the message sender. The message sender then encrypts his or her vote twice, once with the key of the first agent and then re-encrypts the result with the key of the second agent. Finally, the message sender sends the message encrypted twice to the second agent. Because the second agent has sent both keys, he or she is able to decrypt the result with these two keys and make the link between the contents and the sender. This is a problem for secret key encryption and voting except when confidentiality can be ensured by other than cryptographic means.
In order to avoid the above problem, both agents could send their respective keys to the message sender separately. The sender would encrypt his or her message with both keys, and send the encrypted message to the first agent. The first agent would then decrypt the message with the first agent's key, and then forward the partially decrypted message to the second agent. The second agent would then decrypt the message with the second agent's key. At that time, the second agent could read the message, so the message is not private from the second agent. Thus, the second agent knows both the contents of the message (because the second agent decrypted it) and the identity of the sender (because the second agent had distributed the second agent's key to the sender earlier).
An object of the present invention is to enable anonymous communication of messages from senders to a recipient.
Another object of the present invention is to enable anonymous voting.